#!/usr/local/bin/python2.4

# This module implements functionality similar to that found in the
# Icon programming language.  Icon is similar to Python is several
# respects: both are dynamically typed, both have lexical scoping and
# automatic garbage collection.  My goal is to emulate several
# distinctive features found in Icon: the pervasive use of generators
# and result sequences, both iteration and goal-directed
# contexts for evaluation and co-expressions.
#
# At first, I tried to implement Icon functionality directly such that
# Python's evaluation semantics would yield Icon functionality.  For
# example, by overloading the comparison operators for numeric values
# I could make a comparison of icon.integers yield either a value or
# Failure.  However, Python's eagerly evaluates expressions, so I
# cannot think of a way to implement goal-directed evaluation with
# backtracking without defining eval procedures.
#
# My current approach is just to define Icon generators as a class
# and implement functions that perform iteration or goal-directed
# evaluation over them.  This requires uses lots of local functions,
# which can be awkward.  But it does simplify the interface to Python
# because there are no Icon ints or strings to cast back and forth.
#
# It turns out that the Generator class and the every_do function
# implement something very similar to Python generator expressions.
# The only difference I've noticed so far is that Icon style Generators
# detect Failure and continue.  Python generator expressions have a
# condition which prunes out values, but that is not as flexible as
# evaluating the expression and letting it determine success or failure.
# Also, the Python generator expressions evaluate the condition at
# every point in the iteration space.  So if you want to prune the
# iteration space itself, you have to nest generator expressions,
# which is ugly.
#

import types
import string

class TypeException(Exception):
    """A type error within the Icon library"""

class Failure(Exception):
    """Raised when a computation fails and has no result to return"""

# All values are result sequences.  Failure is represented by the end
# of the sequence, which is signalled by Python's StopIteration
# exception.
#
# Since Icon expressions produce a restartable sequence of results, we
# need some extra Python logic around them.  The Generator class captures
# a set of arguments and implements the iterable interface (__iter__(), 
# next() and StopIteration.  Each call to __iter__() produces a new
# Python generator that iterates over the sequence of results.
#
# This class supports 3 categories of sequences:
# 1) Scalars, for which it returns only one result.
# 2) Collections, for which it returns each element in sequence.
# 3) Functions applied to Generators, for which it calls the function
#    once for each point in the iteration space of the argument Generators.
#    Note that the iteration space is determined on the fly and this is
#    where programming with Generators gets interesting.
#
# If you pass multiple arguments to a single Generator, it will iterate
# over them each in order, behaving like Icon's alternation operator.

# Turn on for debugging output
TRACE = False

class Generator:
    """A Generator can return a sequence of results, repeatedly"""

    @classmethod
    def legal_type(cls, x):
        return Generator.scalar_type(x) or Generator.collection_type(x) \
            or Generator.this_type(x)

    @classmethod
    def scalar_type(cls, x):
        t = type(x)
        return (t is int) or (t is float) or (t is str)

    @classmethod
    def collection_type(cls, x):
        t = type(x)
        return (t is list) or (t is tuple) or (t is xrange)

    @classmethod
    def function_type(cls, x):
        t = type(x)
        return (t is types.FunctionType) or (t is types.BuiltinFunctionType)

    @classmethod
    def this_type(cls, x):
        t = type(x)
        return (t is types.InstanceType and isinstance(x, Generator))

    # An icon.Generator is represented by a Python function that
    # captures the underlying value and returns a Python generator
    # over that value.  If there are multiple values, iterate over
    # them in sequence in the manner of Icon's alternation operator.
    def __init__(self, *xs):
        # Check the argument types
        for x in xs:
            if TRACE:
                print "Generator from types", map(type, xs)

            if not Generator.legal_type(x):
                print "The argument type is", type(x)
                raise TypeException

        self.xs = xs
        self.gen = None

    # Create a generator upon request and remember it
    def __iter__(self):
        self.gen = self.start_generator()
        return self

    # Iterate by asking the generator for its next value
    # Failure indicates no value for that point in the
    # iteration space, so keep trying
    def next(self):
        if not self.gen:
            print "Trying to iterate over an exhausted Generator"

        while True:
            try:
                return self.gen.next()
            except Failure:
                pass
            except StopIteration:
                self.gen = None
                raise StopIteration

    def start_generator(self):
        for x in self.xs:
            if TRACE:
                print "Iterate over types", map(type, self.xs)

            if Generator.scalar_type(x):
                if TRACE:
                    print "Scalar yields", x
                yield x

            elif Generator.collection_type(x):
                for elem in x:
                    if TRACE:
                        print "Collection yields", elem
                    yield elem

            else:
                assert Generator.this_type(x)
                # Since x is a Generator, it supports the iterable 
                # interface and we could combine this with the 
                # collection branch
                for elem in x:
                    if TRACE:
                        print "Generator yields", elem
                    yield elem

    # Convert a tuple of arguments to a tuple of Generators over the arguments
    @classmethod
    def convert(cls, *args):
        gens = []
        for arg in args:
            if (type(arg) is types.InstanceType) and isinstance(arg, Generator):
                gens.append(arg)
            else:
                gens.append(Generator(arg))
        return tuple(gens)


# An ApplyGenerator is a Generator that produces the sequence of results
# of a function applied to a set of arguments.  Given the function F(a, b, c)
# and 3 Generators A, B and C, this class will call F once for every tuple
# in the Cartesian product of A x B x C.  Like the base Generator class,
# it can be restarted.
class ApplyGenerator(Generator):
    """An ApplyGenerator can return a sequence of function return values,
       repeatedly"""

    def __init__(self, function, *args):
        if TRACE:
            print "ApplyGenerator from types", function, map(type, args)

        if not Generator.function_type(function):
            print "Type", type(function), "where FunctionType required"
            raise TypeException

        # Convert arguments to Generators
        self.function = function
        self.args = Generator.convert(*args)
        self.gen = None

    # The inherited __iter__() and next() methods should work

    # The apply_fn function does all of the hard work.  Conceptually,
    # there is an iteration space defined on the fly by the Generators
    # stored in self.args.  Since the number of Generators is dynamic,
    # we perform the iteration via recursion, biting off one argument
    # within each call to apply.  We bind the arguments one at a time
    # by defining the "inner" local function and passing it along.

    # Can a function raise the Failure exception to indicate no result?
    # I'm not sure.

    @classmethod
    def apply_fn(cls, expr, *gens):
        if TRACE:
            print "Apply for", len(gens), "Generators"
            print gens

        # In the base case, there are no arguments and we just evaluate
        # the function.
        if len(gens) == 0:
            try:
                value = expr()
                if type(value) is types.GeneratorType:
                    for x in value:
                        yield x
                else:
                    yield value
            except Failure:
                pass

        else:
            # In the general case, we peel off the first Generator, iterate
            # over its value, bind them to a variable x.  We also create a
            # function of arity 1 less that applies the expression to x
            # and N - 1 arguments to be determined later.  We recurse with
            # said function and the remaining Generators.
            def inner(*rest_of_gens):
                return expr(x, *rest_of_gens)

            if len(gens) == 1:
                first_gen = gens[0]
                rest_of_gens = ()
            else:
                first_gen = gens[0]
                rest_of_gens = gens[1:]

            for x in first_gen:
                for result in ApplyGenerator.apply_fn(inner, *rest_of_gens):
                    yield result

    def start_generator(self):
        return ApplyGenerator.apply_fn(self.function, *self.args)


# The apply function creates an ApplyGenerator
def apply(expr, *args):
    return ApplyGenerator(expr, *args)

# Print a collection of results from a Generator
def display(gen):
    print "{" + string.join(map(str, gen), ", ") + "}"

# first_do calls the Generator but returns with the first successful result
def first_do(expr, *args):
    for result in apply(expr, *args):
        return result

# Iterate over a Generator produce all of its results
def every_do(expr, *args):
    for _ in apply(expr, *args):
        pass
